package main

import (
	"fmt"
	//"fmt"
	"math/rand"
	"time"
)

type Skiplist struct {
	Head  *Node
	Level int
}

type Node struct {
	Val     int
	Forward []*Node
}

const p = 0.5
const MaxLevel = 32

func Constructor() Skiplist {
	level := randLevel()
	return Skiplist{Head: &Node{Forward: make([]*Node, MaxLevel)}, Level: level} //注意这里node中使用MaxLevel ，跳表高度是randLevel
}

func randLevel() int {
	level := 1
	rand.Seed(time.Now().UnixNano())
	for rand.Float64() < p && level < MaxLevel {
		level++
	}
	return level
}

func (this *Skiplist) Search(target int) bool {
	x := this.Head
	t := 0
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil && target > x.Forward[i].Val { //找到第一个符合条件的就返回就返回 比如target=3     当前层1 3 3 3 4 当碰到一个3时就不再满足target > x.Forward[i].Val ，继而跳到下一层
			x = x.Forward[i]
			t++
		}
	}

	x = x.Forward[0] //第一层的下一个节点
	if x != nil && x.Val == target {
		return true
	} else {
		return false
	}
}

func (this *Skiplist) Add(num int) {
	x := this.Head
	prev := make([]*Node, MaxLevel)
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil && num >= x.Forward[i].Val { //找相同多个值的最后一个元素
			x = x.Forward[i]
		}
		prev[i] = x
	}

	level := randLevel()
	node := &Node{Val: num, Forward: make([]*Node, level)}

	if level > this.Level {
		for i := this.Level; i < level; i++ {
			prev[i] = this.Head
		}
		this.Level = level
	}

	for i := level - 1; i >= 0; i-- {
		node.Forward[i] = prev[i].Forward[i]
		prev[i].Forward[i] = node
	}

	return
}

func (this *Skiplist) Erase(num int) bool {
	x := this.Head
	flag := false
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forward[i] != nil {
			if x.Forward[i].Val == num {
				tmp := x.Forward[i]
				x.Forward[i] = tmp.Forward[i]
				tmp.Forward[i] = nil
				flag = true
				break //遇到满足条件的node后删除后切换到下一层，对外表现是对于多个相同的num删除时只删一个 这里直接return会有问题，其他层级冗余的元素没有移除
			} else if x.Forward[i].Val < num {
				x = x.Forward[i]
			} else {
				break //这里犯过错 层级查询找不到后结束当前层查询 改下一层 重点！
			}
		}
	}
	return flag
}

func main() {
	obj := Constructor()
	obj.Add(1)
	obj.Add(2)
	obj.Add(3)
	param_1 := obj.Search(0)

	param_3 := obj.Erase(3)
	fmt.Println(param_3, param_1)
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */
